\chapter{语法分析}
语法分析是指对给定的符号串，判定其是否是某文法的句子。通俗讲，就是判定用户源程序中有无语法错误。给定一个用户源程序，通过第四章词法分析方法能够得到源程序对应的单词Token串（即符号串，每一个单词Token可看作一个符号），语法分析的目标是分析该单词Token串是否是某高级程序设计语言文法的句子，即单词Token串是否满足某高级程序设计语言文法。同时，在语法分析的过程中，我们还可以得到用户源程序（单词Token串）的结构，即语法树。

基于文法的语法分析，主要有两类方法，一种是自顶向下的，即基于文法推导的方法，一种是自底向上的，即基于文法进行规约的方法。这两种方法中包含多种算法，在本书中，将介绍自顶向下算法包括递归下降子程序法以及LL(1)方法，自底向上算法包括LR()分析法以及简单优先分析法。

这一章的内容包括语法分析的基本概念，以及常用语法分析方法的设计与实现。

\section{语法分析的基本概念}

给定一个符号串α和一个文法G(Z)，语法分析用于判定α是否是文法G(Z)的句子。基于文法的语法分析，主要有两种方法，一种是自顶向下的，即基于文法推导的方法，一种是自底向上的，即基于文法进行规约的方法。语法分析定义如下：

\begin{definition}
	语法分析是指对给定的符号串α，判定其是否是某文法G(Z)的句子。即
	\begin{figure}
		
		
		%按老师的意思应该是左右俩子图，但是太麻烦了合并吧
		\label{fig:5-1}
	\end{figure}
\end{definition}

1.自顶向下法（推导法）

自顶向下法是从文法的开始符号出发，自顶向下构造语法树，不断地使用文法规则进行推导，即用文法规则的右部替换左部的非终结符，最终试图使树叶全体恰好是给定的符号串α，即对给定的符号串α，判定其是否存在 Z$\stackrel{+}{\longrightarrow}$α；其中：Z是开始符号。我们约定，当一个句型中有多个非终结符可以进行推导替换时，优先替换最左非终结符，即习惯上采用“最左推导法”。


\begin{example}
	给定文法G(E)，给定一个符号串：α=a*(b+c)，判断α是否是文法的合法句子？
	\begin{tcolorbox}[colback=white,colframe=blue!75!black,title=文法定义]
		\centering
		E $\rightarrow$ T | E+T \\
		T $\rightarrow$ F | T*F\\
		F $\rightarrow$ i | (E)\\
		
	\end{tcolorbox}
	
	采用自顶向下的语法分析思路如下：
	\begin{enumerate}
		\item 分析过程：$E\Rightarrow T \Rightarrow T*F  \Rightarrow F*F \Rightarrow a*F \Rightarrow a*(E) \Rightarrow a*(E+T) \Rightarrow a*(T+T) \Rightarrow a*(F+T)  \Rightarrow a*(b+T) \Rightarrow a*(b+F)  \Rightarrow a*(b+c)$
		\item 构造语法树
		\begin{figure}
			\centering
			\input{./chapter5/figures/figure-Derivation-based-syntax-tree}
			\caption{基于推导的语法树}
			\label{fig:5-3}
		\end{figure}
	\end{enumerate}
	\label{ex:5-1}
\end{example}

从上述分析过程不难看出，若分析的第一步不是选择E$\rightarrow$T，而是选择E$\rightarrow$E+T，则将导致分析失败。可见，对于自顶向下的算法，主要解决的是当同一个非终结符有多个产生式时，如何选择正确的产生式进行推导，即自顶向下分析的关键技术是如何确定具有相同左部的产生式之侯选者。

2.自底向上法（归约法）

自底向上法是从给定的符号串α出发，自底向上构造语法树，不断地使用文法规则进行规约，即用文法规则的左部非终结符替换右部的符号串，最终试图使树根是且仅是文法的开始符号，即对给定的符号串α，判定其是否存在 α$\stackrel{+}{\longrightarrow}$Z ；其中：Z是开始符号。我们约定，当一个句型中有多个简单短语可以进行规约时，优先规约最左简单短语，即习惯上采用“最左规约法”。

对于例5.1，我们采用自底向上的语法分析思路如下：
\begin{enumerate}
	\item 分析过程：$a*(b+c)\Rightarrow F*(b+c) \Rightarrow T*(b+c)  \Rightarrow T*(F+c) \Rightarrow T*(T+c) \Rightarrow T*(E+c) \Rightarrow T*(E+F) \Rightarrow T*(E+T) \Rightarrow T*(E)  \Rightarrow T*F \Rightarrow T  \Rightarrow E$
	\item 构造语法树：从树叶向树根方向构造语法树。
	\begin{figure}
		\centering
		\includegraphics[scale=1.0]{./chapter5/figures/figure-Derivation-based-syntax-tree.eps}
		\caption{基于规约的语法树}
		\label{fig:5-3}
	\end{figure}
\end{enumerate}

从上述分析过程不难看出，若分析的第三步不是选择b$\stackrel{\longrightarrow}{.}$F，而是选择T$\stackrel{\longrightarrow}{.}$E，则将导致分析失败。可见，规约也是相同的道理，无论是哪一种自底向上的算法，需要关注它是如何通过当前的句型，来判断句柄，即自底向上分析的关键技术是如何确定当前句型的句柄。

在语法分析过程中，如果没有任何外部支持，很难进行规则的选择判断，而一旦判断错误，就会连锁导致后面的推导失败。最简单的方法，就是利用回溯方法，所谓回溯方法，就是把所有产生式规则都平等对待，随机选一个，走不通再换其他规则，理论上来说一定能找到正确的推导过程，但是效率较低。所以，我们后续讲到的语法分析方法，不论是基于推导的还是基于规约的方法，本质上都是为了提高效率。如果文法不存在二义性，正确的分析过程是唯一的，我们希望找到一种策略，或者一些知识来指导系统，不进行回溯，以提高语法分析效率。

\section{递归子程序法}
递归子程序法，又名递归下降子程序法，是一种自顶向下分析方法，也就是一种基于推导的方法。从开始符号出发，对每一个非终结符，构造一个子程序，用以识别该非终结符所定义的符号串。递归子程序法的重点在于“递归”以及“子程序”。所谓“递归”，就是程序不断地直接调用或间接调用自己。文法的递归性，使得通过有限的产生式，能够表达无限的语句集合。若文法是递归的，则子程序也递归，故称递归子程序。

递归下降子程序法比起回溯方法，能够准确判断每一步推导选用的产生式，没有试错后的回溯，效率有所提升，但由于递归有大量进栈弹栈操作，效率还有进一步提升的空间。该方法的优点在于简单且易于实现。

递归子程序法的关键在于如何选择正确的候选式来完成推导的过程。递归子程序法的基本原理是为文法中每一个非终结符构造一个子程序，来识别产生式右部；子程序以产生式左部非终结符命名，以产生式右部构造子程序内容。


\subsection{递归子程序法示例}

递归子程序法的核心思想是为文法中每个非终结符构造一个子程序，子程序以产生式左部非终结符命名，以产生式右部构造子程序内容。文法中会有很多相同左部的产生式，通常我们将同一个非终结符的产生式，都放到同一个子程序中。

下面通过具体例子来分析递归子程序法的原理。

\begin{example}
	给定文法：A$\rightarrow$aBeD（1）| bAc（2）| $\epsilon$（3），非终结符A对应的递归子程序如图\ref{fig:5-5}所示。
\end{example}
\begin{figure}
	\centering
	\input{./chapter5/figures/figure-Recursive-subroutine-corresponding-in-Example-5-3}
	\caption{例5.3对应的递归子程序}
	\label{fig:5-5}
\end{figure}


其中，NEXT(w)读的是下一个待处理的单词，即token串（token序列）中下一个单词。

在语法分析过程中，我们用当前符，表示正在处理的字符。如图5.5所示，产生式（1）中第一个字母是a，判断当前符是否为a，如果不是，则出错，如果是，则读入下一个字符，再进入子程序B中，对于A这个子程序来说，它并不会去判断B里面的内容，而是直接调用B的子程序，B的子程序负责匹配B生成的串。从B子程序返回后，判断当前符是否为e，与前面类似，如果不是，则出错，如果是，再读入下一个字符，并进入子程序D，从D返回后，即可到达出口.

图5.5所示子程序入口处读入的当前符不是a，则判断是不是b。如果是b，就再取一个字符，然后调用A的子程序。A处理完之后，判断是不是c。如果不是c，则报错；如果是c，那第二个分支执行完毕。

图5.5所示子程序入口处读入的当前符既不是a，又不是b，是不是应该报错呢？假设是f，在这里f不一定是A推出来的，那f为什么能进入到这个程序里呢？可能是这样的情况，例如文法中还有一条产生式C$\rightarrow$Af，可以看出f是由调用A的子程序C生成的；A推出来的是空，因为是C调用A，所以C要处理A后面的f。因此当前符既不是a，又不是b时，可执行子程序中第三条分支，返回到调用子程序A的程序中，由其进行后续处理。

通过上述分析不难看出，同一个非终结符对应的多个产生式放到同一个子程序中，每一个产生式对应子程序中一个分支。

读者可能会对何时读入下一字符存在疑问，这里给出对于接口问题的约定：
\begin{enumerate}
	\item 进入子程序前，当前符已准备好，图中进入子程序B前，准备好了当前符。
	\item 子程序出口前，当前符已读进来，图中判断当前符是否为e，这里的当前符在子程序B中已读入。
\end{enumerate}

接口的约定保证了调用任何一个子程序前，当前符是有效的，即已经读入，但没有被其他程序使用，而当匹配成功后，一定要读入下一字符，更新当前符。如果缺少对于接口的约定，整个程序都会混乱。

接下来，给出使用图5.5所示子程序进行语法分析的示例。
\begin{example}
	给定用户输入符号串α=abed，采用递归子程序法判断符号串α是否能由例5.3中文法推出。
\end{example}

分析：用$\omega$表示当前符。递归子程序入口处首先判断当前符是否为a，而此时当前符$\omega$=a，发现匹配成功，如果当前符不是a，则会进行后续判断。匹配成功后，读入下一个字符，更新当前符$\omega$=b，因为产生式中接下去的字符B是非终结符，非终结符B有自身对应的子程序，因此直接进行调用该子程序，B子程序中具体执行步骤，这里不用考虑。B处理完后，会自动更新当前符$\omega$=e，与产生式中对应进行匹配，如果匹配失败，就出错，发现匹配成功，读入下一个字符，并更新当前符$\omega$=d。产生式中接下去的字符D是非终结符，因此直接进行调用D对应的子程序，如果能从D中正确地返回，就到达出口。

\subsection{递归子程序构造方法}

递归子程序法为每一个非终结符构建一个子程序，为构建一个完整程序，我们还需要一个主程序。给定文法G(E)，其中E为文法初始符。上一节中关于子程序入口，约定进入每一个子程序前，都需要准备好当前符，而利用E产生式构建的子程序作为主程序，会出现缺少当前符问题，因此我们无法将文法初始符的子程序作为主程序。为解决这一问题，我们会增加一个新的产生式Z$\rightarrow$E，这个产生式很简单，左边是一个新的符号，右边是原本的文法初始符。把这个新产生式构造的子程序作为主程序，帮助第一个子程序，读入当前符。
给定一个文法G(E)，其中E为文法初始符。递归子程序构造包括以下几个步骤：
\begin{enumerate}
	\item 扩展文法：定义一个新的产生式Z$\rightarrow$E。把这个新产生式构造的子程序作为主程序，用于将待分析符号串的第一个字符读进来。
	\item 子程序内容设计：
	\begin{enumerate}
		\item 遇到终结符：判断当前符与该终结符是否一致，如果一致，则读下一个字符；
		\item 遇到非终结符：调用非终结符的子程序，在非终结符返回之后不需要再读一个字符，因为返回的时候，已经把下一个待处理的字符读进来了；
		\item 遇到空串：直接连接出口。
	\end{enumerate}
\end{enumerate}


下面举例说明递归子程序构造方法。

\begin{example}
	给定文法G(S): S$\rightarrow$aAb|bS, A$\rightarrow$cd|ε. 试构造该文法的递归子程序。
	
	首先，构造主程序。增加一个新的产生式Z$\rightarrow$S，把这个新产生式构造的子程序作为主程序，帮助第一个子程序S，读入当前符。然后调用原来文法初始符S的子程序，返回后，判断当前符是否为结束符\#，如果不是则出错，如果是则分析成功，程序结束。主程序如下图所示。
	
	\begin{figure}[H]
		\centering
		\input{./chapter5/figures/figure-Main-Program-in-Example-5-4}
		\caption{例5.4的主程序}
		\label{fig:5-6}
	\end{figure}
\end{example}

非终结符S的子程序，如图5.7所示。首先要判断当前符是不是a。如果是a，就再读一个字符（单词），这里调用A的子程序，A执行完之后，无需next(w)函数读下一个字符，因为A的出口会把下一个单词读进来。接着判断b，如果是b，则要把下一个字符读进来。S子程序入口处判断当前符不是a，则判断是不是b，如果是则读下一个字符，然后调用S。调用完S后，不需要再读字符，直接出来就可以。如果既不是a，也不是b，就会报错。

\begin{figure}[H]
	
	\centering
	\begin{minipage}[t]{0.49\textwidth}
		\centering
		\input{./chapter5/figures/figure-Sub-Program-S-in-Example-5-4}
		\caption{例5.4的子程序S}
		\label{fig:5-7a}
	\end{minipage}
	\begin{minipage}[t]{0.49\textwidth}
		\centering
		\input{./chapter5/figures/figure-Sub-Program-A-in-Example-5-4}
		\caption{例5.4的子程序A}
		\label{fig:5-7b}
	\end{minipage}
\end{figure}



非终结符A的子程序，如图\ref{fig:5-7b}所示。先判断当前符是否为c，如果是就读下一个字符，然后判断d。如果不是d就报错，如果是d就接着读，接着就是出口。子程序A入口处当前符如果不是c，就会直接从A的子程序出去，然后在S的子程序里接着判断是否是b。

\subsection{递归子程序法适用范围}
递归子程序是不是适用于所有的语法分析问题呢？我们分析两种情况。
\begin{enumerate}
	\item 如果两个具体有相同左部产生式的第一个字符相同，例如S$\rightarrow$bA|bB，两个产生式首符号均是b，如果当前符是b，此种情况递归子程序无法判断应该选择哪一个产生式。可能的解决方案有：看下一个字符，来判断选择合适的产生式。但是在递归子程序法中，不能往后看一个字符，它只有通过当前符来进行判断。
	
	因此，同一个非终结符的不同产生式，如果它们的首符号相同，则无法设计相应的递归子程序。
	\item 如果文法中有这样一条产生式规则A$\rightarrow$Ab，进了A子程序之后就调用A，无限调用永远不停止，陷入死循环状态。从这里我们可以看出，如果产生式存在直接左递归，就会进入死循环，因此运用递归子程序法的文法中，不允许直接左递归产生式存在。
\end{enumerate}

综上，给定一个文法，如果不存在直接左递归，并且具有相同左部的各产生式，首符号不同，则该文法就可以采用递归子程序的方法进行语法分析。

\begin{example}
	给定文法G(E)，试构造该文法的递归子程序。
	\begin{tcolorbox}[colback=white,colframe=blue!75!black,title=G(E)]
		\centering
		E $\rightarrow$ T | E$\omega_0$T \\
		T $\rightarrow$ F | TE$\omega_1$F\\
		F $\rightarrow$ i | (E)\\
	\end{tcolorbox}
\end{example}


其中产生式E$\rightarrow$E+T和T$\rightarrow$T*F中存在直接左递归，不能直接运用递归子程序法，需要先消除直接左递归。进行消除时，必须保证变换前后是等价的。我们通过文法变换消除左递归，结果如文法G´(E)所示。

\begin{tcolorbox}[colback=white,colframe=blue!75!black,title=G´(E)]
	\centering
	E $\rightarrow$ T \{\ $\omega_0$T\ \} \\
	T $\rightarrow$ F \{\ $\omega_1$F\ \}\\
	F $\rightarrow$ i | (E)\\
\end{tcolorbox}

其中‘\{’和‘\}’是一种特殊的符号，并不是终结符，它表示括号里的内容是可选的，可以是0个，可以是1个或多个。

转换成上述形式后，不存在直接左递归，下面利用递归子程序法进行语法分析。
首先构造主程序。增加一个新的产生式Z$\rightarrow$S，把这个新产生式构造的子程序作为主程序。主程序同图5.6。

非终结符E的子程序如图5.8所示。从入口进入后，先调用T的子程序，因为后边'\{\}'里的内容是可选的，所以从T的子程序返回后，先判断当前符是否为$\omega_0$ ，如果匹配成功，就读入下一字符，调用T的子程序，因为{}里的内容可能有多个，所以从T的子程序返回后，回到判断当前符是否为$\omega_0$ ，当前符不是$\omega_0$ 时，就认为后面不属于该产生式，到达出口。我们发现当前符不是$\omega_0$ 时，可能不是正常结束，而是出现错误，但在递归子程序法中，在出口前的位置，无法判断是否出错，而是让后面的程序来判断是否出错，这是一种滞后报错。

\begin{figure}[H]
	
	\centering
	\begin{minipage}[t]{0.49\textwidth}
		\centering
		\input{./chapter5/figures/figure-Sub-Program-E-in-Example-5-5}
		\caption{例5.5的子程序E}
		\label{fig:5-8}
	\end{minipage}
	\begin{minipage}[t]{0.49\textwidth}
		\centering
		\input{./chapter5/figures/figure-Sub-Program-T-in-Example-5-5}
		\caption{例5.5的子程序T}
		\label{fig:5-9}
	\end{minipage}
\end{figure}

非终结符T和F的子程序，分别如图5.9和5.10所示，具体构造过程，此处不再赘述。


\begin{figure}
	\centering
	\input{./chapter5/figures/figure-Sub-Program-F-in-Example-5-5}
	\caption{例5.5的子程序F}
\end{figure}

递归子程序法在推导过程中，面对同一个非终结符多个产生式，无需回溯，根据当前状态便可自动准确判断应用哪条产生式，其关键在于对文法进行了约束，即同一个非终结符的多个产生式的首符号不相同，且文法不存在直接左递归。递归子程序法简单有效，但它对文法的约束较强，对大量文法的语法分析难以有效。另外，由于递归子程序法其递归性的存在，不断的递归调用，导致整个方法的效率下降。因此，虽然递归子程序法的思路清晰，实现简单，在实际应用中，也往往转化为非递归的方法，从而提高整体效率。



\section{LL(1)文法定义}



上一节中我们提到过，语法分析方法通常分成两大类，分别是自顶向下法（推导法）和自底向上法（归约法）。递归子程序是其中的一种自顶向下的方法。

下面要介绍的是第二种自上而下的方法，也是一种基于推导的方法，叫LL(1)分析法。为什么叫LL(1)分析法？这两个‘L’都是有意义的：第一个‘L’指的是自左向右扫描，即算法（程序）对字符串进行分析的时候是自左向右扫描的；第二个‘L’指的是最左推导，即算法要求推导最左边可推导的非终结符。括号里的“1”指的是在推导过程中，只查看当前的一个符号。为了简单的理解上述内容，我们给出一个例子。\\
\begin{example}
	\label{exp:5-1}
	如有以下文法
	\begin{tcolorbox}[colback=white,colframe=blue!75!black,title=文法定义]
		\centering
		S $\rightarrow$ 主谓宾 \\
		主 $\rightarrow$ 我$|$你$|$它$|$小牛\\
		谓 $\rightarrow$ 研究$|$学习\\
		宾 $\rightarrow$ 主$|$自然语言技术\\
	\end{tcolorbox}
	
	现在需要检查\textbf{目标语句}“小牛研究自然语言技术”是否归属于这个文法，我们从开始符号S出发得到\textbf{分析短语}“主谓宾”。对目标短语从左往右逐个扫描的分析策略是第一个‘L’，对分析短语自左向右推导就是第二个‘L’(具体的说，就是当分析短语存在多个非终结符的时候，我们总是从最左侧的非终结符开始推导)。
	\begin{enumerate}
		\item S $\rightarrow$ 主谓宾
		\item 从目标语句中读入“小”字，确定 主 $\rightarrow$ 小牛
		\item 从目标语句中读入“牛”字，匹配
		\item 从目标语句中读入“研”字，确定 谓 $\rightarrow$ 研究
		\item 从目标语句中读入“究”字，匹配
		\item 从目标语句中读入“自”字，确定 宾 $\rightarrow$ 自然语言技术\\
		....接下来就全是匹配过程
	\end{enumerate}
\end{example}


在上面的分析流程中，我们确定推导式子，只需要读入一个字符即可，这就是LL(1)的1的含义。既然有LL(1)，那么也可以存在让算法观察更多字符来决定选用什么式子进行推导的方法，也就是LL(2)、LL(3)等等。观察更多的字符，对相同左部的产生式右部有相同的前缀会有更多的容忍（允许产生式右部有相同的前缀），比如例\ref{exp:5-1}的‘主’如果还能推导出“小刚”，那我们需要再多看一个字符才能决定主语要推出什么右部。

LL(1)分析法还有一种别的称呼，叫预测分析法。“预测”指的是根据当前的状态，能够知道接下来使用的是哪条产生式。刚才已经提到，LL(1)分析法与递归子程序一样，都是自上而下的，而且是确定性文法的分析方法。对于LL(1)分析法，有三个基本的要点：\\
\begin{tcolorbox}[colback=white,colframe=blue!75!black,title=※\ 三个基本要点]
	\begin{enumerate}
		\item 利用一个分析表，登记如何选择产生式的知识；
		\item 利用一个分析栈，记录分析过程；
		\item 此分析法要求文法必须是 LL(1)文法。
	\end{enumerate}
\end{tcolorbox}
更详细的补充说明上述三点：
\begin{enumerate}
	\item LL(1)分析法必须要有一个分析表，这和递归子程序不一样。分析表的用途是什么？分析表登记了一些如何选择产生式的知识，即在某一个时刻状态下，应该用哪个产生式。
	\item LL(1)分析法里面有一个分析栈，是在执行分析方法的时候用的，目的是记录算法分析的过程，就是要把分析的状态，通过一个栈的形式记录下来。
	\item LL(1)分析法的前置条件是，其所分析的文法必须是LL(1)文法。回顾一下LL(1)文法的两个条件：第一，左部相同的产生式，其右部产生式的首字母不能相同；第二，不能有左递归。
	....接下来就全是匹配过程
\end{enumerate}
\section{LL(1)分析法的完整流程}
\begin{example}一个具体例子的演示
	\\
	\label{exp:5-2}
	
	先对LL(1)文法进行感性的认识。首先，把产生式进行编号。
	\begin{tcolorbox}[colback=white,colframe=blue!75!black,title=G(Z):]
		
		Z $\rightarrow$ dAZ  \ding{172}\quad $|$\quad bAc    \ding{173}   \\
		\quad	A$\rightarrow$aA   \ding{174}\quad $|$\quad $\displaystyle\varepsilon$    \ding{175}
		
		
	\end{tcolorbox}
	四个产生式都进行了编号，其中 \ding{172}、 \ding{173}两个产生式的左部都是Z， \ding{174}、 \ding{175}两个产生式的左部都是A。对于这些产生式，可以得到一个分析表。这个分析表，每一行都对应了一个非终结符，每一列都对应了一个终结符，以及结束的标志‘\#’。
	\begin{table*}[h]
		\centering
		\setlength{\tabcolsep}{7mm}{
			\begin{tabular}{|l|l|l|l|l|l|}
				\hline
				& a & b & c & d & \# \\ \hline
				Z  &   & \ding{173}  &   & \ding{172} &    \\ \hline
				A  & \ding{174} & \ding{175} & \ding{175} & \ding{175} &    \\ \hline
		\end{tabular}}
	\end{table*}
	
	这样的一个表称为分析表，通过一个终结符和一个非终结符，我们就能查到一个表项。表项表示什么？比如，\ding{173}表示的意思是，当非终结符Z，看到了终结符‘b’，就要使用产生式\ding{173}进行推导。其它项以此类推。
	
	有了分析表之后，就可以用LL(1)分析法进行分析。例如对符号串α=“abc\#”进行分析。分析时需要有一个栈结构，记录当前的符号是什么，剩余的符号是什么，操作是什么。
	\begin{figure}[H]
		\centering
		\input{./chapter5/figures/figure-Analysis-process-table-1}
		\caption{对符号串α=“abc\#”的分析过程表}
		\label{fig:1}
	\end{figure}
	首先，要把‘\#’压栈，这是规定。之后还要把起始符号Z压到栈里，因为推导得从起始符号推导。此时，待处理的第一个符号是‘b’，后面的‘a’、‘c’、‘\#’是还没处理的剩余序列。这个时候该如何执行分析方法？栈顶符号是一个非终结符，就用非终结符Z和当前符号‘b’到分析表里进行查找，对应的是产生式\ding{173}这一项，因此就要用产生式\ding{173}进行推导。\\
	\begin{figure}[H]
		\centering
		\input{./chapter5/figures/figure-Analysis-process-table-2}
		\caption{根据栈顶元素和当前符号选择操作2}
		\label{fig:2}
	\end{figure}
	
	下一个操作是让Z出栈，然后把Z的右部“bAc”逆序压栈，即‘c’、‘A’、‘b’依次进栈。因为栈是先进后出的结构，这样‘b’就能在栈顶，可以先匹配，‘A’次之，‘c’最后。现在栈顶符号和当前符号都是‘b’，也是终结符，因此操作就是匹配‘b’。如图 \ref{fig:3}所示。
	\begin{figure}[H]
		\centering
		\input{./chapter5/figures/figure-Analysis-process-table-3}
		\caption{根据当前符号和栈顶元素进行匹配}
		\label{fig:3}
	\end{figure}
	
	
	匹配‘b’之后，就将‘b’出栈，栈顶符号变成‘A’，当前符号是‘a’，剩余序列是‘c\#’。‘A’是一个非终结符，当前符号是‘a’，到分析表里查，得到的对应项是\ding{174}，所以应该用产生式\ding{174}进行推导。如图 \ref{fig:4}所示。
	\begin{figure}[H]
		\centering
		\input{./chapter5/figures/figure-Analysis-process-table-4}
		\caption{根据栈顶元素和当前符号选择产生式}
		\label{fig:4}
	\end{figure}
	
	‘A’推导完后，就把‘A’弹出栈，再把产生式\ding{174}的右部逆序压栈。这时候栈顶是‘a’，当前符号也是‘a’，于是匹配‘a’。如图 \ref{fig:5}所示。
	\begin{figure}[H]
		\centering
		\input{./chapter5/figures/figure-Analysis-process-table-5}
		\caption{根据当前符号和栈顶元素进行匹配}
		\label{fig:5}
	\end{figure}
	
	
	匹配完‘a’后，弹出栈顶符号的同时，当前符号读取下一个，即‘c’，剩余序列只剩一个‘\#’。对于栈顶符号‘A’和当前符号‘c’，查表得\ding{175}。如图 \ref{fig:6}所示。
	\begin{figure}[H]
		\centering
		\input{./chapter5/figures/figure-Analysis-process-table-6}
		\caption{根据当前符号和栈顶元素选择产生式}
		\label{fig:6}
	\end{figure}
	
	这时候选择是空，操作是一样的，把栈顶的非终结符弹出去，右部逆序压栈，空的逆序压栈即没有元素压栈。当前符号是‘c’，所以匹配‘c’。
	
	
	匹配了‘c’之后把栈顶符号弹出去，这时候就剩下‘\#’，当前符号也处理完了，只剩下‘\#’，说明匹配结果是正确的。
	\begin{figure}[h]
		\centering
		\input{./chapter5/figures/figure-Analysis-process-table-7}
		\caption{最终的匹配流程图}
		\label{fig:7}
	\end{figure}
\end{example}
总结一下以上LL(1)分析过程:
\begin{enumerate}
	\item 首先，给文法规则的产生式进行编号，得到一个分析表，分析表的每一行代表一个非终结符，每一列代表一个终结符或表示结束的‘\#’。
	\item 接下来是对符号串α=“bac\#”的分析，先把‘\#’压进栈，然后压入一个起始非终结符，之后就根据栈顶符号和当前符号去查分析表找到要做的操作，弹出栈顶符号并将右部逆序压栈。
	\item 如果栈顶符号和当前符号是相同的终结符，就进行匹配，然后把匹配的元素弹出栈，更新要识别的当前符号。以此类推，直到栈顶符号和当前符号都是‘\#’，即分析正确。
\end{enumerate}

这里有两个问题，分别是:
\begin{tcolorbox}[colback=white,colframe=blue!75!black,valign=scale,halign=center]
	\begin{enumerate}
		\item 选择推导产生式后，为什麽要逆序压栈?
		\item 当栈顶为A,当前单词为c时，为什么选择 A $\rightarrow \varepsilon$?
		
	\end{enumerate}
\end{tcolorbox}



这个地方我不太确定，试着给出这两个问题的答案:
\begin{tcolorbox}[colback=white,colframe=blue!75!black,valign=scale,halign=center]
	\begin{enumerate}
		\item 我们选择一个产生式是通过分析表，而分析表的形成主要是通过相同左部，分析它右部各子产生式最左端不相同的前缀字符形成的。LL1文法从左侧开始扫描目标语句，每次读入一个字符，正好可以和选中的右部子产生式的第一个左侧字符匹配，所以可以发现每次选取非$\varepsilon$的产生式时下一步一定是一个匹配流程。又因为栈是FILO结构，所以逆序压栈才能保证产生式的左端在栈顶。
		\item 栈顶是非终结符号且当前元素不是其产生式的最左字符，说明这个非终结符处理不了这个情况，只能交给栈中在其下的终结符进行匹配或者非终结符进行生成再匹配。这个问题就好像你想要一杯牛奶结果店里只有咖啡，店员不可能收了你的钱给你一杯咖啡，只会让你去找另一个有牛奶的店买牛奶一个道理。
		
	\end{enumerate}
\end{tcolorbox}

\subsection{抽象的流程表示}
\begin{figure}[H]
	\centering
	\input{./chapter5/figures/figure-process-of-LL1}
	\caption{LL1流程}
	\label{fig:8}
\end{figure}


\begin{algorithm}[H]
	\renewcommand{\thealgocf}{}
	\caption{\texttt{LL(1)分析流程}($G,W$)}
	\KwIn{文法集合$G$ 待匹配目标字符串$W$}
	\KwOut{一个状态，接受字符串或者错误}
	先把'\#'和开始符号压入栈中，从目标字符串左侧中读入一个字符。初始化栈结构 $\mathbf{Stack}$，初始化分析表$\mathbf{T}$。
	\\
	\For {$w \in W\quad and\quad w !='\#'$ }
	{            
		\uIf{$Stack.top()$ is $Non-Terminator$}{generate=lookup(T)
			\\Stack.push(generate.reverse())
			\\Stack.pop()
		}
		\uElseIf{$Stack.top() == w$}{
			Stack.pop()
		}
		\Else{\Return ${"Error"}$}
	}
	\uIf{$Stack.pop() != '\#'$}{\Return ${"Error"}$}
	\Return ${"Accept"}$
	
\end{algorithm}
开始
如果栈顶是非终结符，根据当前元素查找分析表选择产生式，弹出栈顶非终结符，逆序将产生式右部压栈。
如果栈顶是终结符，且与当前元素相同则弹出栈顶元素即可。
否则报错。
循环这个过程直到栈顶和当前元素都是'\#'时，认为可以接受，否则报错。

\section{LL(1)文法及其判定}
前面我们说过LL(1)分析依赖于特定的文法特征，大家可以回忆一下前面所提到的三个基本要点的第三点。同时我们还没有给出一个很规范的流程，怎么得到分析表，这依赖于我们即将提出的三个概念。为了更清晰的表达这个概念，我们借助一个具体的文法展开\\
\begin{tcolorbox}[colback=white,colframe=blue!75!black,title=文法定义]
	$G(Z)=(V_N, V_T, Z, P)$\\ \\
	$A\rightarrow\alpha$ $\in$ P,这里的$\alpha$是一个串，可以是终结符也可以是非终结符组成。
\end{tcolorbox}
\subsection{首符号集合、后继符集合与选择符集合}

\begin{definition} 首符号集合
	\begin{tcolorbox}[colback=blue!5!white,colframe=blue!75!black]
		$first(\alpha)=\{t |\alpha \stackrel{*}{\Rightarrow}t...,t\in V_t\}$
	\end{tcolorbox}
\end{definition}





定义在α上，这里α是一个串，是一个产生式的右部。first集的定义就是，所有α能推导出来的串，这些串的串首的终结符所构成的集合称之为α的first集，也叫首符号集合。通俗一点讲就是，把α能推导出来的第一个终结符的集合，称之为α的首符号集合。

\begin{definition}后继符集合
	\begin{tcolorbox}[colback=blue!5!white,colframe=blue!75!black]
		$follow(A)=\{t |Z \stackrel{*}{\Rightarrow}...At...,t\in V_t\}$
	\end{tcolorbox}
\end{definition}


注意，follow集和first集定义的范围不一样，first集是在一个串，也就是产生式右部上定义的，follow集是在左部，也就是非终结符上定义的。A的follow集表示的是A这个非终结符，在推导的过程中，后面能跟哪些终结符。
\begin{definition}选择符集合
	\begin{tcolorbox}[colback=blue!5!white,colframe=blue!75!black]
		
		$$ select(A\rightarrow\alpha)=\left\{
		\begin{aligned}
			&first(\alpha) ,\alpha \stackrel{*}{\nRightarrow}\varepsilon  \\
			&first(\alpha) \cup follow(A) ,\alpha \stackrel{*}{\Rightarrow}\varepsilon
		\end{aligned}
		\right.
		$$
		
	\end{tcolorbox}
\end{definition}
要形成分析表，只需要观察选择集。选择集定义的范围是在产生式上，比前面first集合在产生式右部、follow集在产生式左部的范围更大一些。当整个文法面临一个非终结符和待生成的终结符，选择集告诉我们我们应该选择哪一条产生式进行推导。

一个右侧不能推出空的表达式，他的选择集就是他的first集合，这个理由非常明显，既然右侧不能推出空，最后一定会形成一个只有非终结符的串，那这个非空串的串首字符显然就是这个非终结符在碰到它时应选择什么产生式的凭证。

一个右侧能推出空的产生式，他的选择集多了一个产生式左部的follow集合，这也很好理解，因为当非终结符为空的时候，他不会影响那一个紧挨着他的终结符的推导过程，这也是我们前面所说的去牛奶店买牛奶而不是去咖啡店买牛奶（当然也许咖啡店也卖牛奶）。\\


注:
\begin{enumerate}
	\item $\alpha \stackrel{*}{\Rightarrow}\varepsilon$($\alpha$可空), $\alpha \stackrel{*}{\nRightarrow}\varepsilon$($\alpha$不可空)；
	\item 若$\alpha$=$\varepsilon$则 first($\alpha$)=\{ \}是空集；
	\item 设\#为输入串的结束符，则\#$\in$ follow(Z);
\end{enumerate}
这三条注解其实是偏定义的东西，很难说明为什么要这么做。就第一条来说，能推出空他自己就可以是空，不能推出空他自己不能是空，说这么多就是 \textbf{禁止无中生有}，科学也得遵循哲学指导不是。

第二条定义也非常自然，空了啥玩意都推不出来了，那还有啥终结符呢。这个式子就是告诉我们\textbf{一分耕耘，一分收获}，你今天不播种，那肯定没有收成。理解成物质守恒也行，咋好记你就咋记。

唯独需要小心的是第三条，他很容易被忘记，你可以认为每个文法都隐含着这样一条产生式Z$\Rightarrow$Z\#。Z是开始符号，\#是结束符号，用咱中国人的话说那就是\textbf{有始有终}，建议同学们在科学学习中贯穿哲学文化思想。

\begin{example}一个分析表的构建实例
	
	
	经过这么多的定义，得拿起武器开始干活了。大家也学过编程，这个像分段函数一样的选择集定义，在编程上就是个if-else的分支结构。所以我们拿到一个产生式的时候，得先去做个判断，判断产生式的右侧能不能为空，我们不需要很严谨的把整个产生式都推导到全是终结符，一旦出现一个终结符，就说明右侧不为空了，因为终结符不能继续推导，这个就是\textbf{赚来的钱，交的朋友都可能会离开你，他们是非终结符;学到的知识是终结符，它永远空不了}。
	
	
	
	我们从这个文法中说明怎么形成分析表
	\\
	
	
	\begin{tcolorbox}[colback=white,colframe=blue!75!black,title=G(Z):]
		
		Z $\rightarrow$ dAZ \ding{172}\quad $|$\quad bA   \ding{173}   \\
		\quad	A$\rightarrow$aA  \ding{174}\quad $|$\quad $\displaystyle\varepsilon$   \ding{175}
		
		
	\end{tcolorbox}
	
	\ding{172}显然不为空，因为出现了非终结符d；\ding{173}显然不为空，因为出现了非终结符b；\ding{174}同理不为空；\ding{175}为空。
	
	不为空的\ding{172}\ding{173}\ding{174}，select集合就是first集，分别是d、b、a。
	
	能为空的\ding{175}，select集合是first集与follow集的并集，但是因为他不是能为空，而是本身是空，根据上面的“物质守恒”原则，他的first集也是空，他的follow集合就是d和b以及\textbf{\#}，这个地方可能有点难，我给你们推荐个经验，先从别的产生式里面找到这个非终结符，如果非终结符后头跟的是终结符，直接塞进follow集，如果跟的是非终结符，把这个后头的非终结符的first集塞进follow集合即可。所以A这个非终结符，出现在了\ding{172}\ding{173}中。在\ding{172}中，其后跟的是非终结符，把Z的first集合也就是\{d,b\}加入A的follow集合。其次是'\#'，这个根据我们前面提到的“有始有终”原则，所有的开始符号后面都隐含跟随着一个'\#'号，所以\ding{173}中可以认为是 Z $\rightarrow$ Z\# $\rightarrow$ bA\#，于是A的follow集合就还有\#号。
	
	到这个地方，select集其实就是分析表的等价表示，如果你还没想明白怎么从select集构建分析表，你需要下去花点功夫，当然也许睡一觉起来就想明白了。这个分析表的结果在上面LL1的分析例子中给出来了。
\end{example}

\subsection{LL(1)文法及其判定}
\begin{definition}LL(1)文法
	\begin{tcolorbox}[colback=white,colframe=blue!75!black,title=]
		
		
		LL(1)文法是指文法中，具有相同左部的产生式，其select集合没有交集
		
	\end{tcolorbox}
	
\end{definition}

这个文法是递归子程序法和LL(1)分析法的使用前提。因为一旦相同左部的产生式的select集有交集，我们就不知道在面对一个元素的时候需要选择哪一条产生式，也就是出现了歧义。

我们举一个新的例子，\\
\begin{tcolorbox}[colback=white,colframe=blue!75!black,title=G(Z):]
	
	Z $\rightarrow$ Zb \ding{172} \quad $|$ \quad a  \ding{173} 
	
	
\end{tcolorbox}

$$ 
\because\\
\left .
\begin{aligned}
	select(\textcircled{1})={a} \\
	select(\textcircled{2})={a}
\end{aligned}
\right \}\quad Selection\ set\ intersection
$$
这两个产生式的选择集合相交了，就不属于LL(1)文法了。这里也能看到，在递归子程序里，不能有左递归，一旦有左递归，选择集合一定会相交。具有左递归的文法，一定不是LL(1)文法！那有左递归，该怎么办呢？我们可以尝试把左递归改写成右递归形式。

再扩展一下，左递归有两种，一种是直接左递归，一种是间接左递归，上面的例子是直接左递归，这两种左递归都需要消除。一个通用的算法，如下

\begin{algorithm}
	\caption{消除左递归算法}
	\label{alg:5-1}
	以某种顺序排列非终结符A1，A2，……，An；\\
	\For{int i = 1; i<=n; i++}{\For{int j = 1; j<=i-1; j++}{将每个形如 Ai → Ajγ 的产生式替换为产生式组 Ａi → ξ1γ｜ξ2γ｜……｜ξkγ ，
			其中，Aj→a1｜a2｜……｜ak是所有的当前Aj产生式}}
	
	消除关于Ai产生式中的直接左递归性
	\}
\end{algorithm}
转换为右递归文法后，select集不相交了\\
\begin{tcolorbox}[colback=white,colframe=blue!75!black,title=G'(Z):]
	\centering
	Z$\rightarrow$aA \ding{172}\\           A$\rightarrow$bA \ding{173}$|$ $\varepsilon$ \ding{174}
	
	
\end{tcolorbox}
$$ 
\left .
\begin{aligned}
	select(\textcircled{2})={b} \\
	select(\textcircled{3})={\#}
\end{aligned}
\right \}
$$
$\therefore$ G'(Z)是LL(1)文法，可以使用LL(1)分析。

\section{LL(1)分析器设计(实现)}
分析器由两部分构成，第一部分是分析资源，在LL(1)分析里面就是分析表，第二部分是程序，程序通过读分析表来完成分析过程。
简单的说，就是构建分析表，和利用分析表解析待识别串。
\begin{tcolorbox}[colback=blue!5!white,colframe=blue!75!black]
	\centering
	LL(1)分析表 + LL(1)控制程序
	
	
\end{tcolorbox}
%\clearpage % 换页，\newpage也可以，推荐\clearpage
\subsection{LL(1)分析表的构造}
LL(1)分析表是存储文法选择集合的知识表。表列是终结符，行是非终结符，每个元素是产生式序号。展示一下C++版本的一些粗糙思路供同学们参考。
\begin{lstlisting}[language=C++]
	struct Element{
		int number;	//产生式序号
	}
	//这两个Map需要一段初始化程序，根据你选择的输入方式决定，本质上就是一段从字符串里分离 $\rightarrow$ 左右部分的处理。选择使用map是因为需要一个从char到int的映射，才方便从表里存取表项，很自然的，我们还需要维护两个int类型的index变量，来为每一个独立的char进行一个index++的初始化。这段地方留给同学们自己想想。
	Map<char,int> terminator;
	Map<char,int> Nterminator;
	Element L[terminator.size()][Nterminator.size()];
	//数据结构定义到这里了仍然存在一些小问题，那就是我们该怎么记录产生式，不然我们拿到了序号也没有意义，当然我们可以不存序号，将element类里改成string类型，直接存下产生式的右部，还有很多选择，我就不赘述了，这个地方同学们后期做编译原理课设会有很多机会去实现的。
\end{lstlisting}
这个地方的代码是我根据PPT的意思写的，不太符合工程实现的感觉。你也可以按你喜欢，觉得更工程的方法来完成这个步骤。
如果你已经把数据结构的定义和初始化想好了，那我们可以开始下一个问题，也就是分析表的初始化。这个需要我们去求first和follow集合，还是挺有挑战性的。我是这么想的，如果对编程不熟悉的同学，可以考虑手动输入每个产生式的first和follow集合；如果编程能力比较强的同学，可以尝试自动从产生式里解析出来first和follow集合，因为后期课设的产生式非常多非常丰富，如果纯靠脑袋去想会很累，当然最重要的是很不酷。

我给出一点我的想法，希望是启发，不是约束。我尽可能避开具体的代码，只给出注释。
\begin{lstlisting}[language=C++]
	map<char,set<char> firstSet;
	void genFirstSet(){
		//先初始化终结符的firstset，当然是自身。
		for(){
			//遍历终结符集合，逐个插入对应的firstSet中
		}
		
		//这里是难度重头戏，需要遍历产生式，为非终结符生成firstSet，我建议流程是这样的。
		// 这里应该有一个循环
		while(){
			// 取出产生式的左部，去firstSet里面拿到其对应的firstSet，可能是空，也可能是不完整的firstSet，也可能是完整的。
			//判断这个产生式的右部是不是终结符或者是空，且是否存在这个左部的firstSet中，不在就加入
			//否则如果是非终结符，判断右部第一个字符能不能是空，如果能，就把他的firstSet复制过来，继续往后看，这里应有一个循环。
			//如果右侧第一个非终结符不空，那直接复制firstSet就好
			//这里还有个小困难，就是如何结束这个循环，我建议是当没有改变时逃出，通过维护一个bool变量，在有改变的分支里不断变换他的值，在循环一开始改动他的值。
		}
	}
	
\end{lstlisting}

first集合的自动生成大概如上所示，一个定义的不错的结构，会让你的思路事半功倍，如果做完first集合生成，相信follow集合也不会难倒你.加油.


接着是生成select集合，这个地方根据上面的定义做就好。在做完这一切，得到分析表之后，你可以看一下
\begin{figure}[H]
	\centering
	\input{./chapter5/figures/figure-process}
	\caption{流程图}
	\label{fig:9}
\end{figure}

我们回头再梳理一遍要做的事情
\begin{enumerate}
	\item 消除左递归
	\item 生成firstSet
	\item 生成followSet
	\item 生成selectSet
	\item 生成分析表
	\item 借助控制程序进行分析
\end{enumerate}

\section{LR()分析法的介绍}
\subsection{LR()分析法的“统治地位”}
LR分析是当前最一般的分析方法。因为它对文法的\textbf{限制最少}，现今能用上下文无关文法描述的程序设计语言一般均可用LR方法进行有效的分析。而且在分析的效率上也不比诸如不带回溯的自顶向下分析、一般的“移进归约”以及算符优先等分析方法逊色。\\
\begin{tcolorbox}[colback=white,colframe=blue!75!black,title=上下文无关文法的简要回顾]
	
	上下文无关文法就是说这个文法中所有的产生式左边只有一个非终结符，很多人可能对上下文这个概念一知半解，我举一个反例。aZc$\rightarrow$abZbb，当我们需要匹配'Z'的时候，需要确保这个'Z'的两侧有正确的上文'a'和下文'c'，这个就是上下文有关文法。
	
	
\end{tcolorbox}
LR(1)分析是我们重点关注的内容，与以前的分析方法依赖的文法包含关系如图 \ref{fig:10} 所示。需要说明，LR(0)和LL(1)没有包含关系，但是有交集。
\begin{figure}[H]
	\centering
	\includegraphics[scale=0.8]{./chapter5/figures/figure-The-relationship-between-the-three-grammars-of-inclusion.eps}
	\caption{常见的三种文法的包含关系}
	\label{fig:10}
\end{figure}
一些课外的扩展知识研究中提到一个由LR(K)文法产生的语言均可以等价的由某一LR(1)文法产生，这也是我们为什么在课程只研究k $\le$ 1的情况，因为对于程序编译基本够用了，感兴趣的同学可以自行查找证明资料。我在编纂这个的过程也找到了一个对LL分析和LR分析进行对比的blog\footnote{https://blog.reverberate.org/2013/07/ll-and-lr-parsing-demystified.html},也可供同学们做课外读物之用。
\subsection{LR()分析法的定义}
LR( )分析法是指从左到右扫描、最左归约(LR)之意；它属于自底向上分析方法。推导和归约是一对互逆的过程，推导是从非终结符产生零到多个终结符的过程，归约则是从多个终结符逆推回开始符号的过程。相信在上一节LL(1)分析法刚刚接触过扫描和推导的读者，应该不会对这个表述很陌生。

在本节学习中，我们需要认识LR(0)，掌握LR(1)分析，括号中的数字是需要看几个\textit{当前元素}才能决定归约产生式的意思，和LL(1)中的'1'没有什么不同。


为了让同学们更深入的理解最左归约和最左推导这个LR和LL分析法唯一的不同,我们会给出一个例子。但是在此之前,我需要先介绍两个概念.\\


\begin{tcolorbox}[colback=white,colframe=blue!75!black,title=略显晦涩的定义]
	
	短语:如果有 $S\stackrel{*}{\Rightarrow} \alpha A \delta$\ 且$A\stackrel{+}{\Rightarrow}\beta$,则称$\beta$是句型$\alpha A \delta$关于非终结符A的短语。特别的，如果$A\Rightarrow\beta$，则称$\beta$是句型$\alpha A \delta$关于非终结符A的\textbf{直接短语}。\\
	句柄：一个句型的最左直接短语称为该句型的句柄。
	
\end{tcolorbox}
最左归约的任务就是要在扫描特定数量的元素之后，确定当前句型的\textbf{句柄}。

接着到具体的例子上，展示一个LR()分析过程，注意不是LR(1)\\
\begin{tcolorbox}[colback=white,colframe=blue!75!black,title=文法定义]
	$G(Z)=(V_N, V_T, Z, P)$\\
	
	$Z\rightarrow aBAd$,\ $A\rightarrow bc|c$,\ $B\rightarrow bB|c$
\end{tcolorbox}
符号串$ abccd $最左归约过程:
\begin{enumerate}
	\item 读入a，没法归约，此时存着a
	\item 读入b，没法归约，此时存着ab
	\item 读入c，此时存着abc，其中的c可以被归约成B，也就是$B\leftarrow c$，归约完后存着abB。这里是一个难点，会有同学思考为什么不是$A \leftarrow bc$，从而只存着aA。
	\item 读入c，此时存着abBc，$B\leftarrow bB$，归约完后存着aBc
	\item 读入d，此时存着aBcd，$A\leftarrow c$，归约完后存着
	\item 最后$Z\leftarrow aBAd$，归约结束
\end{enumerate}
整个流程是\\
\begin{tcolorbox}[colback=white,colframe=blue!75!black]	
	\begin{enumerate}
		\item $ab\underline{c}cd\rightarrow a\underline{bB}cd \rightarrow aB\underline{c}d \rightarrow \underline{aBAd} \rightarrow Z$
		
		\item $a\underline{bc}cd\rightarrow aA\underline{c}d \rightarrow aABd $ 无法进行下去了
	\end{enumerate}
	
\end{tcolorbox}
我们可以解释一下第二条路径为什么行不通，上面的短语定义有一个前提，那就是开始符号能推出这个串，但是aAcd并不能被开始符号Z推出。从语法树角度来说，一个短语应该是从语法树的叶节点开始，囊括一个完整的子树，如果从这个角度思考，b和c同为叶节点，但是他们之间并没有通路，所以不能算是一个完整的子树，既然不是短语，那就不会是句柄了。图 \ref{fig:11}中展示了按序号顺序构建语法树的过程。
\begin{figure}[H]
	\centering
	\includegraphics[scale=0.8]{./chapter5/figures/figure-The-syntax-tree-formed-by-the-leftmost-reductive-convention.eps}
	\caption{最左归约形成的语法树}
	\label{fig:11}
\end{figure}
我们用规整的数据结构来表示上面的最左归约过程
\begin{figure}[H]
	\centering
	\input{./chapter5/figures/figure-LR1-analysis-process}
	\caption{分析栈记录的分析过程}
	\label{fig:12}
\end{figure}

\subsubsection{句柄识别器的构造}
在具体程序中，我们需要找到更简单的方法来辨别目前保存的串中是否有句柄。我们通过标注产生式右部的文法符号位置的扩展文法实现(同时还用一个新的开始符号替换了旧的开始符号)。\\
\begin{tcolorbox}[colback=white,colframe=blue!75!black,title=文法定义]
	扩展前
	$Z\rightarrow aBAd$,\ $A\rightarrow bc|c$,\ $B\rightarrow bB|c$\\
	扩展后\\$Z'\rightarrow Z_1$ \large{\textcircled{\small{0}}}\normalsize\enspace , $Z\rightarrow a_2B_3A_4d_5$ \ding{172} ,\ $A\rightarrow b_6c_7$ \ding{173}$|c_8$ \ding{174},\ $B\rightarrow b_9B_{10}$\ding{175} $|c_{11}$ \ding{176}\\
\end{tcolorbox}
这么做的好处在于，同一个c，$c_8$和$c_{11}$就不会在归约时产生歧义，从不同位置归约就不一样了。我们把他们的位置当做状态，构建自动机来识别句柄。

具体的做法如下，我们假设开始状态都是0，有了状态，自动机还需要状态转移方程$\delta(state.token)=next\_state$才完整。
构建完成的自动机如图 \ref{fig:13}所示。其中移进状态是0、2、3、4、6、9,在这个状态下需要继续读入字符，才能判断下一步行为。归约状态是5、7、8、10、11，在这个状态下可以进行归约操作。接受状态是1，OK表示归约结束。我们用刚刚识别abccd\#的过程举个例子，以$b_9B_{10}$来说，当到达归约状态时弹出$b_9B_{10}$，回到2状态，2状态见到B就到了3状态，别的就没什么不好理解的地方了。

\begin{figure}
	\centering
	\input{./chapter5/figures/figure-Automatics-1}
	\caption{自动机}
	\label{fig:13}
\end{figure}
\begin{figure}[H]
	\centering
	\input{./chapter5/figures/figure-Identification-Chart}
	\caption{句柄自动机运用后的识别图}
	\label{fig:14}
\end{figure}
句柄识别器又称“活前缀图”：意思是在最左归约过程中，识别了句柄，实际上也就识别了以句柄为后缀的该句型（规范句型）的前部符号串。

\section{LR(0)分析器设计}
有了自动机（句柄识别器）后，就能做自底向上的分析，就可以构建一个LR(0)分析器。LR(0)分析器跟LL(1)分析器非常像，由两部分构成：第一部分，分析表，即自动机，涵盖了识别句柄也就是活前缀图的信息；第二部分是控制程序，程序要读取分析表，同时根据用户输入的词串进行分析。再强调一下，LR(0)中的0，是指不必查看当前符号就可确认句柄的意思。LR(0)分析法要求文法应是LR(0)文法。
\begin{figure}[H]
	\centering
	\input{./chapter5/figures/figure-Basic-components-of-LR0-analyzer}
	\caption{LR(0)分析器的基本组成}
	\label{fig:15}
\end{figure}
\subsection{LR(0)文法及其判定}
满足下述特点的文法称为LR(0)文法：
\begin{enumerate}
	\item 句柄识别器中，移进和归约不冲突；即移进和归约不同时发生。
	\item 归约时不查看当前符号。
\end{enumerate}
\subsection{LR(0)分析表构造}
LR()分析表是LR()分析法的知识表，是句柄识别器的一种机内表示形式：
纵轴表示既有终结符和‘\#’，又有非终结符，因为LR()分析里状态的转移之间读入的符号，既可能是终结符，也可能是非终结符。
横轴表示的是状态编码，代表对状态的编号，0表示起始。
\begin{figure}[H]
	\centering
	\input{./chapter5/figures/figure-LR0-analysis-table}
	\caption{LR(0)分析表}
	\label{fig:16}
\end{figure}
接下来要根据句柄识别器，填写表格里的表项。如果当前状态是i，读入x，到达k，即$\delta(i,x)=k$就把xk填到相应的表项里，x既可以是终结符也可以是非终结符，k表示的是到达的目标状态。如果是归约态，则把这一行全写成归约，不管后面出现什么符号，都要归约。如果在1状态看到“\#”，就是ok。用形式化的语言描述如下：
\begin{figure}[H]
	\centering
	\input{./chapter5/figures/figure-Description-of-LR0-analysis-table-construction-algorithm}
	\caption{LR(0)分析表构建算法描述}
	\label{fig:17}
\end{figure}
在下面这个文法上实操一下
\begin{tcolorbox}[colback=white,colframe=blue!75!black,title=文法定义]
	$Z'\rightarrow Z_1$ \large{\textcircled{\small{0}}}\normalsize\enspace , $Z\rightarrow a_2B_3A_4d_5$ \ding{172} ,\ $A\rightarrow b_6c_7$ \ding{173}$|c_8$ \ding{174},\ $B\rightarrow b_9B_{10}$\ding{175} $|c_{11}$ \ding{176}\\
\end{tcolorbox}
他的自动机图\ref{fig:13}我们已经在上面给出过，其分析表按算法填完如下图：\begin{figure}[H]
	\centering
	\input{./chapter5/figures/figure-Example-of-analysis-table}
	\caption{分析表实例}
	\label{fig:18}
\end{figure}
\subsection{LR(0)控制程序设计}
\begin{figure}[H]
	\centering
	\input{./chapter5/figures/figure-Control-program-flow-chart}
	\caption{控制程序流程图}
	\label{fig:19}
\end{figure}
\section{项目集和可归约前缀图}
下面讲另一种句柄识别器的构造方法，即用项目集的方式构造。
\subsection{扩展文法}
假设有一个文法G(Z)，要构造它对应的句柄识别器，有以下的步骤：
先将原始文法加入位置信息和替换开始符号，形成扩展文法。加入Z`->Z，引入Z`，目的是让程序能够启动。这个技巧在递归子程序也讲过，起始的主程序要读入一个字符，保证进入子程序之前已经读了一个字符。接着对所有产生式右部的所有符号进行编号，包括终结符和非终结符，编号没有特别的要求，可以任意编号，编号只代表状态。
\begin{figure}[H] 
	\begin{minipage}[t]{0.5\linewidth} 
		\centering 
		\input{./chapter5/figures/figure-Original-Grammar}
		\caption{原始文法} 
		\label{frame} 
	\end{minipage}% 
	\begin{minipage}[t]{0.5\linewidth} 
		\centering 
		\input{./chapter5/figures/figure-Extended-Grammar}
		\caption{扩展文法} 
		\label{label} 
	\end{minipage} 
\end{figure}
\subsection{由扩展文法构造可归约前缀图（句柄识别器）}

首先把Z`$\rightarrow$·Z放到项目集里,·后面是非终结符Z，把Z的产生式$Z \rightarrow \cdot aBAd$写到下面，形成$I_0$状态。

$I_0$状态把$\cdot$后移一位，可以读入Z或者a，读入Z形成Z`$\rightarrow Z\cdot$，也就是$I_1$状态，我们把这个状态称作OK状态,代表解析正常结束，是一个结束态。

对于$I_0$状态还可以读入a，形成$I_2$状态，接下来希望看到B。因此，我们把B的产生式附着在$I_2$后面，形成了$I_2$状态。
\begin{figure}[H]
	\centering
	\input{./chapter5/figures/figure-Project-set-map}
	\caption{项目集图}
	\label{fig:22}
\end{figure}


对于$I_2$状态，现在可以读入B，形成$I_3$状态，遇见B之后希望看到A，所以把A的表达式也接在$I_3$后面，形成了$I_3$状态。

我们通过四个状态的形成的例子，表达了前缀图的形成原则，$\cdot$后紧跟着的非终结符或终结符是我们希望预见的符号，所以如果是非终结符，我们需要把他的产生式加入新的状态中，因为是归约，是从句柄慢慢回到开始符号，句柄在句法树的底端都是终结符。如果是终结符，直接后移预见符号即可。
最后形成
\begin{figure}[h]
	\centering
	\input{./chapter5/figures/figure-Automata-formed-by-prefix-maps}
	\caption{由前缀图形成的自动机}
	\label{fig:23}
\end{figure}
\subsection{由可归约前缀图构造LR(0)分析表}
得到这样一个自动机后，就可以构造LR()分析表。0状态看到Z到1状态，就把“Z1”写到0行Z列所在的表项。1状态看到\#，代表结束，即OK。5状态稍微麻烦一点，I5表示对产生式（1）进行归约，就把这一行全写成“r(1)”，表示不看当前字符，全部进行归约。其它同理。
\begin{figure}[H]
	\centering
	\input{./chapter5/figures/figure-LR0-analysis-table-1}
	\caption{LR(0)分析表}
	\label{fig:24}
\end{figure}
\subsection{LR(0)分析法过程示例}
LR()分析是一个移进归约算法，有一个栈，只有两个操作，一是往栈里压入一个符号，二是对栈顶符号进行归约。通过自动机，就能知道用哪个操作。
首先，先压入“\#0”，表示起始状态，然后读入一个符号到w，注意w是待处理的下一个符号，还未压入栈中。剩余串为“bccd\#”。0状态看到a，通过查分析表，到2状态，做移进操作PUSH(a2)，a是待处理的符号，2是当前状态编号。a被压入栈了，当前w为空，所以读入下一个符号b，剩余串为“ccd\#”。2状态看到b，查表，到9状态，则PUSH(b9)，并读入下一个字符c，剩余串为“cd\#”。当前状态是9状态，看到c，到11状态，所以PUSH(c11)。11状态是一个归约态，要用产生式（5）B->c进行归约，即把栈顶的c11归约成B。c被归约后，弹出栈，当前栈顶是9号状态，看到被归约后的B，查表得B10，写到栈顶。现在到了10状态，仍然是归约态，用产生式（4）B$\rightarrow$bB归约 ，即把“b9B10”弹出，在2状态看到被归约出的B，查表得B3，到3状态。3状态看到c，查表得c8，做移进操作，PUSH(c8)。接下来的分析同理，这里不一一赘述。
\begin{figure}[H]
	\centering
	\input{./chapter5/figures/figure-LR0-analysis-process}
	\caption{LR(0)分析过程}
	\label{fig:25}
\end{figure}
\subsection{LR(0)分析法实例}
做一个小练习，对于黄色框的文法，构造可归约前缀图。
\begin{figure}[H]
	\centering
	\input{./chapter5/figures/figure-LR0-grammar-description}
	
	\label{fig:26}
\end{figure}
\begin{figure}[H]
	\centering
	\input{./chapter5/figures/figure-Handle-Identifier}
	\caption{句柄识别器}
	\label{fig:28}
\end{figure}

\begin{figure}[H]
	\centering
	\input{./chapter5/figures/figure-Attributable-prefix-chart}
	\caption{可归约前缀图}
	\label{fig:27}
\end{figure}
\begin{figure}[H]
	\centering
	\input{./chapter5/figures/figure-lr0-analysis}
	\caption{LR(0)分析表}
	\label{fig:29}
\end{figure}
\section{LR(0)分析法的扩展}
LR()分析要求文法是LR()文法，LR()文法有两个最基本的要求。第一，对于任何一个状态，不能产生移进/归约冲突，即不能既有移进操作又有归约操作。也不能有归约/归约冲突，即一个终止状态有两个产生式可以归约，这样在实现系统的时候是无法执行的，因为不知道是归约还是移进。
\begin{figure}[H]
	\centering
	\input{./chapter5/figures/figure-handle-recognizer-conflicts}
	\caption{句柄识别器的冲突}
	\label{fig:30}
\end{figure}
此时，LR(0)分析法失效，因为产生了歧义，需要改造句柄识别器的构造方法。第一种改造方法，把LR(0)分析表进行简单的扩展，称为SLR(1)分析法。
如何把LR(0)简单地扩展一下，变成SLR(1)方法呢？从字面意思理解，S表示简单，没有太复杂的操作，括号里的1表示要看待处理字符w才知道要做什么操作。

看一个两个非终结符Z、A的文法例子\\
\begin{tcolorbox}[colback=white,colframe=blue!75!black,title=文法定义]
	
	$Z\rightarrow aAb$,\ $A\rightarrow cd|\varepsilon$,\ 
\end{tcolorbox}
1. 扩展文法，构造句柄识别器

写成如黄色框所示的扩展形式，画成自动机。
\begin{figure}[H]
	\centering
	\input{./chapter5/figures/figure-lr0-extended-grammar}
	
	\label{fig:31}
\end{figure}
\begin{figure}[H]
	\centering
	\input{./chapter5/figures/figure-automaton-from-extended-grammar}
	
	\label{fig:32}
\end{figure}
这个自动机跟以前的自动机相比，多了一个空（$\varepsilon$），2状态看到空串到7状态，是一个归约产生式（3）的状态。从2状态到7状态不需要读符号，进行确定化之后，可以把7状态删除，将7状态进行归约的操作放到2状态执行，即2状态是一个终止态，要归约产生式（3）。这时候就产生了移进/归约冲突，2状态既可以移进c，也可以归约产生式（3）。这样当到2状态的时候，就不知道该到3状态或5状态，还是直接归约产生式（3）。
\begin{figure}[H]
	\centering
	\input{./chapter5/figures/figure-move-in-convention-conflict}
	\caption{移进/归约冲突}
	\label{fig:33}
\end{figure}


这里的解决方法有两种思路，一是变换文法，但是在LR()分析里变换文法并不方便，因为变换文法后的自动机并不能直接看出来。二是改变方法，在2状态的时候，一个关键的决策是如何知道要归约产生式（3）？在LR(0)的时候，不需要看待处理的符号w再进行归约。反过来说，如果能够看w，就能知道是不是要进行归约。这里思考一下，w是什么？是归约完的符号后面跟的符号，比如，w是a，栈顶如果能归约成A的话，A后面马上就能跟a，所以w是归约的左部（非终结符）的follow集的元素。在2状态的时候，如果想用规则（3）进行归约，则要求下一个符号是规则（3）左部对应的follow集，即{b}。如果在2状态要归约产生式（3）到A，下一个符号只能是b。2状态能移进的符号只有c，到5状态。反过来说，b代表要进行归约操作，c代表要移进下一个符号。Follow集跟移进操作的集合不一样。
\begin{figure}[H]
	\centering
	\input{./chapter5/figures/figure-solve-method}
	\caption{解决方法}
	\label{fig:34}
\end{figure}
2. 扩展句柄识别器，构造SLR(1)分析表

把这个过程用项目集的方式写出来。图中红色的部分$A \rightarrow \cdot \varepsilon$，可直接写出归约。对于$I_2$状态，有两种操作，看到b则归约，看到c则移进。这种方式称为SLR(1)文法，在2状态需要看w才能决定要不要归约，其它状态不需要看。
\begin{figure}[H]
	\centering
	\input{./chapter5/figures/figure-reducible-prefix-graph}
	\caption{可归约前缀图}
	\label{fig:35}
\end{figure}
它的分析表比较好写，唯一要注意的是2状态，之前的分析表是一整行都要写归约，因为不需要看w。在SLR(1)里，需要看w，当w是b的时候，归约产生式（3），是c的时候移进。注意这里与LR(0)分析表的区别，当是归约态是，LR(0)里一整行都要归约，而SLR(1)不是。其它部分与LR(0)一样。
\begin{figure}[H]
	\centering
	\input{./chapter5/figures/figure-slr1-analysis-extension}
	\caption{分析表}
	\label{fig:36}
\end{figure}
\section{SLR(1)分析法的扩展}
尽管查看当前单词，SLR(1)方法仍然对许多文法的LR(0)项目集合中存在的状态冲突不能解决。比如，产生移进/归约冲突，follow集里的元素包括移进的元素，这时候就不能说要归约该元素，因为有可能要移进。
如果集合带有交集，就要对SLR(1)进一步进行扩展。
看一个例子。
\begin{figure}[H]
	\centering
	\input{./chapter5/figures/figure-slr1-analysis-table}
	\label{fig:37}
\end{figure}
\subsection{扩展文法}
\begin{figure}[H]
	\centering
	\input{./chapter5/figures/figure-extend-grammar}
	\label{fig:38}
\end{figure}

\subsection{构造可归约前缀图}首先是S`到S，能归约出S的产生式有四个：（1）、（2）、（3）、（4），都写下来。对于$I_0$状态，可以跳转到3个状态。第一种情况，可以看到S，到OK状态，即结束态。第二种情况，看到a，希望看到a的是$S\rightarrow\cdot aAd , S\rightarrow\cdot acc$，把这两条产生式的·往后移一位，分别表示看到a后希望看到Ad，以及看到a后希望看到ec。A是非终结符，所以把A的产生式写下来。对于$I_2$状态，可能看到两种情况，A或e。如果看到A，就到I3状态，再看到d，则到结束态$I_4$。如果看到e，把$S\rightarrow a\cdot ec,A\rightarrow \cdot e$的·往后移一位，得到状态$I_5$。$I_5$这两个产生式含义不一样，$S \rightarrow ae\cdot c$表示希望看到c，$A\rightarrow e\cdot$表示要进行归约，归约的是产生式（5）。再看到c就到$I_6$状态。同理，在$I_0$状态看到b，也能得到类似的结果。

\begin{figure}[H]
	\centering
	\begin{tikzpicture}
		%------------------------------------------------------------------------------------
		%    图片1.4
		\tikzstyle{rec} = [draw, fill=orange!20, align=center, align=center]
		\tikzstyle{white rec} = [draw, minimum width=12em, minimum height=2em, align=center, thick]
		\tikzstyle{arr shape} = [draw=red!70,ultra thick, shape=single arrow, minimum height=3em, single arrow tip angle=90, single arrow head extend=0.5em, scale=0.5]
		\tikzstyle{arr tri} = [draw=red!, ->, line width=0.3em]
		\tikzstyle{call} = [draw, align=center, shape = rectangle callout, fill=purple!10, rounded corners, anchor=south, minimum height=2em]
		
		\newcommand{\Xshift}{4em}
		
		% 节点
		% 第一列
		\node[rec] (I0) at (0,0) {
			$S'\rightarrow \cdot S, \quad\#$
			\\$S\rightarrow \cdot aAd, \quad\#$
			\\$S\rightarrow\cdot aec, \quad\#$
			\\$S\rightarrow \cdot bAc,\quad\#$
			\\$S\rightarrow \cdot bed,\quad\#$};
		% 第二列
		\node[rec] (I1) at (8.8em,3.1em) {$S'\rightarrow S\cdot,\quad\#$};
		\node[rec] (I2) at (9.45em,-1em) {$S\rightarrow a\cdot Ad,\quad\#$
			\\$S\rightarrow a\cdot ec,\quad\#$
			\\$A\rightarrow\cdot e,\quad d$
		};
		\node[rec] (I7) at (9.45em,-9.6em) {$S\rightarrow b\cdot Ac,\quad\#$
			\\$S\rightarrow b\cdot ed,\quad\#$
			\\$A\rightarrow \cdot e,\quad c$};
		
		% 第三列
		\node[rec] (I3) at (19.45em,-1em) {$S\rightarrow aA\cdot d,\quad\#$};
		\node[rec] (I5) at (19.45em,-6em) {$S\rightarrow ae\cdot c,\quad\#$
			\\$A\rightarrow e\cdot,\quad d$};
		\node[rec] (I8) at (19.45em,-10em) {
			$S\rightarrow bA\cdot c,\quad\#$};
		\node[rec] (I10) at (19.45em,-14em) {
			$S\rightarrow be\cdot d,\quad\#$
			\\$A\rightarrow e\cdot ,\quad c$};
		
		% 第四列
		\node[rec] (I4) at (29.45em,-1em) {
			$S\rightarrow aAd\cdot,\quad\#$};
		\node[rec] (I6) at (29.45em,-5em) {
			$S\rightarrow aec\cdot,\quad\#$};
		\node[rec] (I9) at (29.45em,-10em) {
			$S\rightarrow bAc\cdot,\quad\#$};
		\node[rec] (I11) at (29.45em,-14em) {
			$S\rightarrow bed\cdot,\quad\#$};
		
		% 箭头尝试
		\draw[->,black,thick] (3.5em,3.08em)--node[above]{S}(I1.west);
		\draw[->,black,thick] (3.5em,-1em)--node[above]{a}(I2.west);
		\draw[->,black,thick] (I0.south)|-node[left]{b}(I7.west);
		\draw[->,black,thick] ([xshift=0em,yshift=0em]I2.east)--node[above]{A}(I3.west);
		\draw[->,black,thick] (I2)|-node[left]{e}(I5);
		\draw[->,black,thick] ([xshift=0em,yshift=-0.41em]I7.east)--node[above]{A}(I8.west);
		\draw[->,black,thick] (I7)|-node[left]{e}(I10);
		
		
		\draw[->,black,thick] (I3)--node[above]{d}(I4);
		\draw[->,black,thick] ([xshift=0em,yshift=+1em]I5.east)--node[above]{c}(I6);
		\draw[->,black,thick] (I8)--node[above]{c}(I9);
		\draw[->,black,thick] (I10)--node[above]{d}(I11);
		
		
		% 浮动文字
		\node(I0W)at ([xshift=2.4em,yshift=4em]I0) {$I_0$};
		\node(I1W)at ([xshift=2.4em,yshift=1.5em]I1) {$I_1$};
		\node(OK)at ([xshift=5em,yshift=0em]I1) {$OK$};
		\node(I2W)at ([xshift=2.4em,yshift=2.6em]I2) {$I_2$};
		\node(I3W)at ([xshift=2.4em,yshift=1.5em]I3) {$I_3$};
		\node(I4W)at ([xshift=2.4em,yshift=1.5em]I4) {$I_4$};
		\node(r1)at ([xshift=5em,yshift=0em]I4) {$r(1)$};
		\node(I5W)at ([xshift=2.4em,yshift=2.1em]I5) {$I_5$};
		\node(r5)at ([xshift=-4.5em,yshift=-1em]I5) {$r(5)$};
		
		\node(I6W)at ([xshift=2.4em,yshift=1.5em]I6) {$I_6$};
		\node(r2)at ([xshift=5em,yshift=0em]I6) {$r(2)$};
		\node(I7W)at ([xshift=2.4em,yshift=2.6em]I7) {$I_7$};
		\node(I8W)at ([xshift=2.4em,yshift=1.5em]I8) {$I_8$};
		\node(I9W)at ([xshift=2.4em,yshift=1.5em]I9) {$I_9$};
		\node(r3)at ([xshift=5em,yshift=0em]I9) {$r(3)$};
		\node(I10W)at ([xshift=2.4em,yshift=2.1em]I10) {$I_{10}$};
		\node(r5w)at ([xshift=-4.5em,yshift=-1em]I10) {$r(5)$};
		
		\node(I11W)at ([xshift=2.4em,yshift=1.5em]I11) {$I_{11}$};
		\node(r4)at ([xshift=5em,yshift=0em]I11) {$r(4)$};
		
		
		
		%------------------------------------------------------------------------------------
	\end{tikzpicture}
	\caption{可归约前缀图}
	\label{fig:5-25}
\end{figure}

这里出现的问题是，在I5和I10状态分别出现了冲突，既有归约又有移进。看归约产生式的左部的follow集是否跟移进操作相交，比如这里follow(A)={c,d}，即\{c\}$\cap$\{c,d\}$\neq \emptyset$,\{d\}$\cap$\{c,d\}$\neq \emptyset$，不能用SLR(1)，查看“当前单词”不能解决冲突。

解决思路：对有冲突的状态，仍然是查看‘当前单词’，但要看的更精确一点，以确定动作。
（*）构造LR(1)可归约前缀图
还是用项目集的方式，但是在产生式后面加一个符号，这个符号表示如果这个产生式被归约了，它后面应该出现什么符号，比如说I0状态第一条产生式S'$\rightarrow$$\cdot$S,如果S被归约成了S`，那么S`后面应该跟着\#。注意这里跟follow集不一样。如果S被推导完了，即S'$\rightarrow$S$\cdot$，那么后面也跟着\#，如I1状态。在I0状态时，读入a，产生式S$\rightarrow$$\cdot$aAd的·往后移一位，得S$\rightarrow$a$\cdot$Ad，后面的符号也是\#。产生式S$\rightarrow$$\cdot$aec同理。对于I2项目集，S$\rightarrow$a$\cdot$ Ad中的A怎么得到？只有产生式（5）能归约出A。如果e出现了，归约出A，A后面应该跟什么符号？A后面只有跟d，才能做推导，即A$\rightarrow$$\cdot$e,d。在$I_2$看到e之后，到I5，并没有产生移进/归约冲突，因为w如果是d，就归约A$\rightarrow$e$\cdot$，如果不是，就移进c。虽然c在A的follow集里，但不代表在I5状态里看到c就要进行归约，因为进行归约的前置条件是，在I2状态时A后面跟一个d，因此，只有在I5状态里A$\rightarrow$e$\cdot$这个推导完后，必须跟d，才需要进行归约。
\begin{figure}[H]
	\centering
	\begin{tikzpicture}
		%------------------------------------------------------------------------------------
		%    图片1.4
		\tikzstyle{rec} = [draw, fill=orange!20, align=center, align=center]
		\tikzstyle{wr} = [draw, align=center, align=center]
		\tikzstyle{white rec} = [draw, minimum width=12em, minimum height=2em, align=center, thick]
		\tikzstyle{arr shape} = [draw=red!70,ultra thick, shape=single arrow, minimum height=3em, single arrow tip angle=90, single arrow head extend=0.5em, scale=0.5]
		\tikzstyle{arr tri} = [draw=red!, ->, line width=0.3em]
		\tikzstyle{call} = [draw, align=center, shape = rectangle callout, fill=purple!10, rounded corners, anchor=south, minimum height=2em]
		
		\newcommand{\Xshift}{4em}
		
		% 节点
		% 悬空1
		\node[wr] (l) at(8em,10em){
			
			$I_{10}$：移进符号集合$——{d}$,\\
			\ 	规约符号集合$——{c}$,\\
			$\because {d}\cap{c}=\emptyset$\\
			$\therefore$ 查看当前单词$w$\\
			若$w=d$,则c11\\
			若$w=c$,则r(5)
			
			
		};
		\node[wr] (r) at(22em,10em){
			
			$I_{5}$：移进符号集合$——{d}$,\\
			\ 	规约符号集合$——{c}$,\\
			$\because {d}\cap{c}=\emptyset$\\
			$\therefore$ 查看当前单词$w$\\
			若$w=d$,则r(5)\\
			若$w=c$,则c6
			
			
		};
		% 第一列
		\node[rec] (I0) at (0,0) {
			$S'\rightarrow \cdot S, \quad\#$
			\\$S\rightarrow \cdot aAd, \quad\#$
			\\$S\rightarrow\cdot aec, \quad\#$
			\\$S\rightarrow \cdot bAc,\quad\#$
			\\$S\rightarrow \cdot bed,\quad\#$};
		% 第二列
		\node[rec] (I1) at (8.8em,3.1em) {$S'\rightarrow S\cdot,\quad\#$};
		\node[rec] (I2) at (9.45em,-0.6em) {$S\rightarrow a\cdot Ad,\quad\#$
			\\$S\rightarrow a\cdot ec,\quad\#$
			\\$A\rightarrow\cdot e,\quad d$
		};
		\node[rec] (I7) at (9.45em,-9.6em) {$S\rightarrow b\cdot Ac,\quad\#$
			\\$S\rightarrow b\cdot ed,\quad\#$
			\\$A\rightarrow \cdot e,\quad c$};
		
		% 第三列
		\node[rec] (I3) at (19.45em,1em) {$S\rightarrow aA\cdot d,\quad\#$};
		\node[rec] (I5) at (19.45em,-6em) {$S\rightarrow ae\cdot c,\quad\#$
			\\$A\rightarrow e\cdot,\quad d$};
		\node[rec] (I8) at (19.45em,-10em) {
			$S\rightarrow bA\cdot c,\quad\#$};
		\node[rec] (I10) at (19.45em,-14em) {
			$S\rightarrow be\cdot d,\quad\#$
			\\$A\rightarrow e\cdot ,\quad c$};
		
		% 第四列
		\node[rec] (I4) at (29.45em,1em) {
			$S\rightarrow aAd\cdot,\quad\#$};
		\node[rec] (I6) at (29.45em,-5em) {
			$S\rightarrow aec\cdot,\quad\#$};
		\node[rec] (I9) at (29.45em,-10em) {
			$S\rightarrow bAc\cdot,\quad\#$};
		\node[rec] (I11) at (29.45em,-14em) {
			$S\rightarrow bed\cdot,\quad\#$};
		
		% 箭头尝试
		\draw[->,black,thick] (3.6em,3em)--node[above]{S}(I1);
		\draw[->,black,thick] (3.6em,-0.8em)--node[above]{a}(I2);
		\draw[->,black,thick] (I0.south)|-node[left]{b}(I7.west);
		\draw[->,black,thick] ([xshift=0em,yshift=1.5em]I2.east)--node[above]{A}(I3.west);
		\draw[->,black,thick] (I2)|-node[left]{e}(I5);
		\draw[->,black,thick] ([xshift=0em,yshift=-0.5em]I7.east)--node[above]{A}(I8.west);
		\draw[->,black,thick] (I7)|-node[left]{e}(I10);
		
		
		\draw[->,black,thick] (I3)--node[above]{d}(I4);
		\draw[->,black,thick] (I5)--node[above]{c}(I6);
		\draw[->,black,thick] (I8)--node[above]{c}(I9);
		\draw[->,black,thick] (I10)--node[above]{d}(I11);
		
		
		% 浮动文字
		\node(I0W)at ([xshift=2.4em,yshift=4em]I0) {$I_0$};
		\node(I1W)at ([xshift=2.4em,yshift=1em]I1) {$I_1$};
		\node(OK)at ([xshift=5em,yshift=0em]I1) {$OK$};
		\node(I2W)at ([xshift=2.4em,yshift=2.4em]I2) {$I_2$};
		\node(I3W)at ([xshift=2.4em,yshift=1em]I3) {$I_3$};
		\node(I4W)at ([xshift=2.4em,yshift=1em]I4) {$I_4$};
		\node(r1)at ([xshift=5em,yshift=0em]I4) {$r(1)$};
		\node(I5W)at ([xshift=2.4em,yshift=2.4em]I5) {$I_5$};
		\node(r5)at ([xshift=-4em,yshift=-1em]I5) {$r(5)$};
		
		\node(I6W)at ([xshift=2.4em,yshift=1em]I6) {$I_6$};
		\node(r2)at ([xshift=5em,yshift=0em]I6) {$r(2)$};
		\node(I7W)at ([xshift=2.4em,yshift=2.4em]I7) {$I_7$};
		\node(I8W)at ([xshift=2.4em,yshift=1em]I8) {$I_8$};
		\node(I9W)at ([xshift=2.4em,yshift=1em]I9) {$I_9$};
		\node(r3)at ([xshift=5em,yshift=0em]I9) {$r(3)$};
		\node(I10W)at ([xshift=2.4em,yshift=1.8em]I10) {$I_{10}$};
		\node(r5w)at ([xshift=-4em,yshift=-1em]I10) {$r(5)$};
		
		\node(I11W)at ([xshift=2.4em,yshift=1em]I11) {$I_{11}$};
		\node(r4)at ([xshift=5em,yshift=0em]I11) {$r(4)$};
		
		
		
		%------------------------------------------------------------------------------------
	\end{tikzpicture}
	\caption{完整的可归约前缀图}
	\label{fig:5-26}
\end{figure}

解决办法：

当项目$I_j$(例如$I_2$)中同时含有$A\rightarrow \alpha\cdot B\beta$和$B\rightarrow \cdot Y$时，则向前看一个符号$a$,只有$a\in First(\beta)$时，才能进行$B\rightarrow Y$归约。


3. 构造LR(1)分析表


在每个有可能产生冲突的地方进行标注，在LR(1)里所有归约的地方，都要用一个符号来记录，看到w的哪个元素进行归约。红色{}里表达的意思是，我出现这个符号的时候需要进行归约。比较特殊的是I5和I10状态，分别看到d和c需要进行归约，否则就是$I_5$读入c到$I_6$，或$I_{10}$读入d到$I_{11}$。{\#}表示归约的条件，看到\#就归约。LR(1)并没有像LR(0)那样，如果归约一行全是r，要多看一个w。
基于这样一个想法，就很容易把LR(1)分析表写出来，在4状态的时候，标准的LR(0)在一行全都要归约，但LR(1)要看w，只有w是\#的时候才需要归约。5状态比较特殊，看到c的时候到6状态，看到d的时候归约产生式（5）。这里LR(1)一行不只有归约，还有移进，和SLR(1)一样。判断是移进还是归约，看后面可能跟的元素，在这个集合里就归约，不在就移进。

\section{简单优先分析法基本概念}
\subsection{什么是简单优先分析法}
简单优先分析法是一种从左到右扫描、最左归约分析法。简单优先和LR()分析的策略是一样的，都是从左到右扫描，最左归约。它属于自底向上的分析方法。到现在已经了解了两种自下而上的分析方法，LR()分析和简单优先分析。分析的目的是进行归约，要找句柄。简单优先分析法找句柄的方法与LR()分析不一样，LR()是用句柄识别器，做一个自动机，进行归约。简单优先利用文法符号之间的优先关系来确定待归约的句柄，来确定当前句型的句柄。
简单优先分析法的基本要点有三：

（1）利用一个分析表，登记选择句柄产生式的知识；

（2）利用一个分析栈，记录分析过程；

（3）“分析算法”依次读取单词，并进行如下操作：当栈顶出现句柄是，归约之，否则移进。所以简单优先分析也是一个移进归约的方法。

跟LR()分析不同的是判断句柄出现的方法，LR()分析时根据句柄识别器的状态，简单优先分析要根据分析表里的一些规则或关系。
\subsection{简单优先分析过程示例}
设有文法：
\begin{figure}[H]
	\centering
	\input{./chapter5/figures/figure-Simple-Priority-Analysis-Grammar}
	\label{fig:45}
\end{figure}
现分析符号串$\alpha=abbeae\#$，求分析树。
首先，从S开始，由产生式S->aAeB，可推导出
\begin{figure}[H]
	\centering
	\input{./chapter5/figures/figure-Analysis-Tree-1}
	
	\label{fig:46}
\end{figure}
这里有两个非终结符，A和B，分别进行进一步的推导。A推导出S和b，S进一步推导出b；B推导推导出a和A，A再推导出e。
\begin{figure}[H]
	\centering
	\input{./chapter5/figures/figure-Analysis-Tree-2}
	\label{fig:47}
\end{figure}
这棵树对应了文法推导的过程，如果是自下而上就是归约的过程。

利用分析栈记录行分析过程

首先，往栈里放一个\#，当前待处理的符号w是a，栈顶不能归约，所以移进a，w读取下一个符号b。还是没有句柄，继续移进b，w读b，注意此时栈里是第一个b，w是第二个b。此时出现句柄，b要归约成S。w里还是b，栈顶没有句柄了，移进，读取下一个符号e。这时又出现句柄Sb，归约。依次类推，不断进行归约操作，得到最终结果。

\begin{figure}[H]
	\centering
	\input{./chapter5/figures/figure-Analysis-of-symbol-string-table}
	\label{fig:48}
\end{figure}
这个过程跟LR()分析的过程很相似，唯一区别在求句柄的地方。何时栈顶出现句柄？怎样求当前句柄产生式？
\subsection{文法符号之间的优先关系}
\subsubsection{归约过程中如何确认句柄?}
是否是句柄，还要看其所在符号串中的位置。句柄要在产生式的右部，产生式右部与树有什么样的关系呢？
首先，树是有层次的，底下的符号要比上面的符号先归约。如下图，第\ding{175}层要比第 \ding{174}层先归约，第 \ding{174}层比第\ding{173}层先归约，第\ding{173}层比第\ding{172}层先归约。
\begin{figure}[H]
	\centering
	\input{./chapter5/figures/figure-Analysis-tree-with-numbers}
	
	\label{fig:49}
\end{figure}
从语法树上，找出优先关系（指相邻符号之间）如下：

\ding{172}同时归约者为相等关系，记作$\equiv$

\ding{173}左后归约者为小于关系，记作$<\cdot$。优先关系的小于号，左侧晚于右侧归约。

\ding{174}左先归约者为大于关系，记作$\cdot>$

这些符号的左和右的含义并不是代数上的等号、小于号和大于号的含义，左和右分别表示连续出现的两个符号左边那个符号和右边那个符号。对于例子b$\cdot>$b，前一个b表示的是连续出现两个符号左边那个符号是b的情况，后一个b表示连续出现两个符号右边那个是b的情况。表示如果连续出现两个b，左边的b要早于右边的b先归约。

假如知道了任意两个符号的大于、等于、小于关系，就能把关系符号填到一个串任意两个符号中间，特殊的一点是这里面最左边和最右边的\#是约定，表示字符串的起始和结束。
最左边和最右边的\#比所有符号都小。
\begin{figure}[H]
	\centering
	\input{./chapter5/figures/figure-Priority-relationship-of-the-string-of-symbols-to-be-analyzed-1}
	\caption{待分析符号串的优先关系}
	\label{fig:50}
\end{figure}
中间的画横线的部分，b被夹在中间，这里的b对应语法树左下角的b。b与左侧的a是<的关系，与右侧的b是>的关系，意思是比左边（右边）先规约，即它应该先规约。
\begin{figure}[H]
	\centering
	\input{./chapter5/figures/figure-Analysis-Tree-3}
	
	\label{fig:51}
\end{figure}
归约完后，b变成了S，即
\begin{figure}[H]
	\centering
	\input{./chapter5/figures/figure-Priority-relationship-of-the-string-of-symbols-to-be-analyzed-2}
	
	\label{fig:52}
\end{figure}
语法树变成：
\begin{figure}[H]
	\centering
	\input{./chapter5/figures/figure-Analysis-Tree-4}
	
	\label{fig:53}
\end{figure}
左下角的a与S的关系是，S比a要先归约，S与b的关系是$\equiv$，同时归约，b要先于上面的e归约，所以S和b要被归约，归约成A，即
\begin{figure}[H]
	\centering
	\input{./chapter5/figures/figure-Priority-relationship-of-the-string-of-symbols-to-be-analyzed-3}
	
	\label{fig:54}
\end{figure}
得到的树如图：
\begin{figure}[H]
	\centering
	\input{./chapter5/figures/figure-Analysis-Tree-5}
	
	\label{fig:55}
\end{figure}
此时被归约的是划横线的e，归约成A，接着再把a、A、e、B归约。
\begin{figure}[H]
	\centering
	\input{./chapter5/figures/figure-Priority-relationship-of-the-string-of-symbols-to-be-analyzed-4}
	
	\label{fig:56}
\end{figure}
总结：一个句型的句柄，位于第一次（自左至右）出现在<和>之间的符号串，且要求该符号串之间的关系是$\equiv$。
\subsubsection{优先关系的定义}
\begin{figure}[H]
	\centering
	\input{./chapter5/figures/figure-Simple-Priority-Relationship-Grammar-1}
	
	\label{fig:57}
\end{figure}
从文法中获取优先关系。设$s_i$，$s_j$是两个文法符号。

\ding{172}如果产生式右部连续出现的符号是si和sj，那si和sj相等，即$s_i\equiv s_j$。

\ding{173}如果产生式右部推导出符号si，si后面跟着非终结符W，W经过若干次推导，推导出的符号是sj，即sj要被归约成W，就说sj是早于si归约的，即$s_i<\cdots_j$。比如，S$\rightarrow$aAeB$|$d中，A推导出的第一个符号要早于a归约。

\ding{174}如果一个非终结符V右边跟着符号sj，V推导出的最后一个符号si，si要早于sj归约，即$s_i>s_j$

\begin{figure}[H]
	\centering
	\input{./chapter5/figures/figure-Priority-Relationship-image}
	\caption{}
	\label{fig:58}
\end{figure}

\subsubsection{头符号集合和尾符号集合}
头符号集合指一个非终结符通过推导出现的第一个符号是什么。头符号集合不要求集合里的元素都是终结符，所有的符号都可以推导出。尾符号集合指非终结符推导出的串的最后一个符号是什么。这个定义和select集、first集、follow集是不一样的。在LL(1)分析的时候，select集要求的是推导出来的终结符，头符号集合和尾符号集合没有这个要求，所有的符号都行。
\begin{figure}[H]
	\centering
	\input{./chapter5/figures/figure-Symbolic-formal-representation}
	\caption{头符号集合和尾符号集合的形式化表述}
	\label{fig:59}
\end{figure}

\begin{example}
	
\end{example}

\begin{figure}[H]
	\centering
	\input{./chapter5/figures/figure-Definition-of-grammar}
	\caption{文法定义}
	\label{fig:60}
\end{figure}
\subsubsection{求头符号和尾符号集合}

根据$S\rightarrow aAeB|b$，S的头符号集合是{a，b}。B和b属于S的尾符号集合，B是一个非终结符，B的尾符号集合也属于S的尾符号集合。根据$B\rightarrow aA$，B的尾符号集合是{A}。A也是一个非终结符，A的尾符号集合也属于S的尾符号集合，A的尾符号集合是{b，e}。综上，S的尾符号集合是{B，b，A，e}。

根据$A\rightarrow Sb|e$，S和e属于A的头符号集合。S是非终结符，S的头符号集合{a，b}属于A的头符号集合。A的尾符号集合是{b，e}。

同理，B的头符号集合是{a}，尾符号集合是{A，b，e}。
\begin{figure}[H]
	\centering
	\input{./chapter5/figures/figure-Symbol-table}
	
	\label{fig:61}
\end{figure}
\subsubsection{优先矩阵}
得到了头符号集合与尾符号集合之后，就可以求优先关系。优先关系体现在优先矩阵里，优先矩阵准确描述了任意两个符号之间的优先关系。纵轴表示关系符号左边的符号，横轴表示右边的符号。比如图中S所在行，A所在列的表项，填的是左边出现S ，紧接着右边出现A，它们两个之间的优先关系。优先关系矩阵的横轴和纵轴是一样的，而且所有终结符和非终结符都要写上。
\begin{figure}[H]
	\centering
	\input{./chapter5/figures/figure-Priority-Matrix}
	\caption{优先矩阵}
	\label{fig:62}
\end{figure}
如何填该表？根据优先关系的定义，产生式连续出现两个符号，就是$\equiv$；如果一个终结符，一个非终结符，非终结符的头符号集合和左边的终结符构成<关系，非终结符的尾符号集合和右边的终结符构成>关系。


具体看一下。首先看产生式$S\rightarrow aAeB| b$，推出一个符号就不用考虑了，因为至少要两个符号。先看aA，是$\equiv$关系，注意这里填的是a所在行，A所在列，表示a在左边，A在右边，而不是A所在行，a所在列。A是一个非终结符，a跟在非终结符A后面，那a要晚于A的头符号集合归约，填上<。

接着往后看Ae，A和e是$\equiv$关系，往A所在行，e所在列的表项填上$\equiv$。左边是非终结符A，右边是终结符e，A的尾符号集合要早于右边出现的e归约。A的尾符号集合是{B，e}，所以B和e要早于e归约。千万不要把左右两个符号的顺序弄反了，Ae的e出现在右侧，所以这个e要按照纵列去查，而A的尾符号集合要按表中左侧的行去查。

这里有个问题，为什么e>e？如果左边出现e，右边同样出现e，表示左边的e先归约，这里不是指两个相同符号的代数运算，表达的是优先关系。

同理，其它符号的关系也可以填上。
\begin{figure}[H]
	\centering
	\input{./chapter5/figures/figure-Filled-priority-matrix}
	\caption{填好的优先矩阵}
	\label{fig:63}
\end{figure}
表中空的地方表示确定不了两个符号之间的优先关系，这个方法用不了。

\section{简单优先分析器设计}
有了优先矩阵表，就可以实现简单优先分析器。
\begin{figure}[H]
	\centering
	\input{./chapter5/figures/figure-Priority-analyzer}
	\label{fig:64}
\end{figure}
简单优先虽然简单，但有适用的范围。
\subsection{简单优先文法及其判定}
满足下述特点的文法称为简单优先文法：
\ding{172}文法产生式没有相同的右部。不能同时有A推出α以及B推出α。
在归约的时候，看到的是一个赋值串，有一个句柄要归约，但在简单优先分析里不知道要归约成什么。要想知道用什么归约，只能到归约机里查，查到哪个产生式就用哪个产生式，如果查到两个产生式右部是相同的，就可以用两个产生式进行归约，就会不知道用哪一条来归约。

\ding{173}文法符号之间至多有一种优先关系。
\subsection{简单优先分析矩阵分析表构造}
首先，制作表格如下
\begin{figure}[H]
	\centering
	\input{./chapter5/figures/figure-Priority-Analysis-Table}
	
	\label{fig:65}
\end{figure}
算法：
\ding{172}如果产生式右部连续出现两个符号，填$\equiv$

\ding{173}如果产生式右部出现了一个非终结符W，它和它左边的符号si就构成了<关系，所有si小于W的头符号集合的元素。

\ding{174}如果产生式右部出现的非终结符V，V后面跟着一个符号sj，V的尾符号集合的元素和sj构成了>关系。
\begin{figure}[H]
	\centering
	\input{./chapter5/figures/figure-Formal-description-of-the-construction-of-a-simple-priority-analysis-table}
	\caption{简单优先分析矩阵分析表构造的形式化描述}
	\label{fig:66}
\end{figure}
\subsection{简单优先控制程序设计}
先把\#压栈，再读一个符号w，然后查表，看当前栈顶符号和w的优先关系。当前栈顶符号Xk是左边的符号，w是右边的符号，查表里是否为空，如果为空表示出错，如果不为空就看是否是，表示的意思是Xk早于w归约，有可能出现句柄。如果不是，就判断是否要结束 ，即只剩“\#S\#”，如果还没结束，就接着移进。如果是，就要归约，找离最近的的中间部分，用sisi+1...sj表示，把sisi+1...sj弹出，用相应左部的符号替换。这里注意，归约完后，不能移进，w只是帮助判断栈顶是否出现句柄，还未处理（压栈）。
\begin{figure}[H]
	\centering
	\input{./chapter5/figures/figure-Simple-Priority-Process}
	\caption{简单优先控制程序}
	\label{fig:67}
\end{figure}
\section{算符优先分析}
\subsection{算符文法}
算符优先要求文法的右部不能连续出现两个非终结符，比如右部不能出现A后面跟着B，这样就不能叫算符优先。如果文法里产生式右部没有连续出现的非终结符，就有可能是算符优先文法。
\begin{figure}[H]
	\centering
	\input{./chapter5/figures/figure-OG-Grammar-Definition}
	
	\label{fig:68}
\end{figure}
\subsection{头符号集合和尾符号集合}
如何定义算符优先？我们重新定义一下头符号集合和尾符号集合。头符号集合不只包含P推导出来的串首终结符，而且包含推导出来的串首是非终结符的终结符，例如，A->aB，A=>abB，A=>Bac，这三个产生式的a都属于头符号集合，换句话说，不需要考虑非终结符，来确定头符号集合。尾符号集合同理，不考虑非终结符。
\begin{figure}[H]
	\centering
	\input{./chapter5/figures/figure-Collection-of-symbols}
	\caption{头符号集合和尾符号集合}
	\label{fig:69}
\end{figure}
\subsection{算符优先关系定义}
跟上面一样，两个符号连续出现就是$\equiv$。如果出现了像aQb这种情况，a和b的关系也是$\equiv$。注意，在算符优先文法里，不考虑非终结符，可以看成a和b是连续的。

$<$除了要考虑p$\rightarrow$...aR...，还要考虑头符号集合的定义和尾符号集合的定义。
\begin{figure}[H]
	\centering
	\input{./chapter5/figures/figure-Definition-of-operator-priority-relations}
	\caption{算符优先关系定义}
	\label{fig:70}
\end{figure}
\subsection{算符优先文法}
如果算符文法G中的任何一对终结符a和b之间，仅满足上述一种关系，则G就是一个算符优先文法（OPG）。
\begin{example}
	
	
	求文法G(E)是简单优先文法吗？先写出头符号集合和尾符号集合，然后把优先矩阵写出来。
	
	
	\begin{figure}[H]
		\centering
		\input{./chapter5/figures/figure-Simple-Priority-Grammar-Example}
		\label{fig:71}
	\end{figure}
	
	\begin{figure}[H]
		\centering
		\input{./chapter5/figures/figure-Set-of-head-and-tail-symbols}
		\caption{头符号集合和尾符号集合}
		\label{fig:72}
	\end{figure}
	
	\begin{figure}[H]
		\centering
		\input{./chapter5/figures/figure-Priority-Matrix-1}
		\caption{优先矩阵}
		\label{fig:73}
	\end{figure}
	
	
	简单优先文法有两个条件，不能有相同右部的产生式，任意两个符号之间的关系只能有一种。矩阵有不唯一的关系，所以文法G(E)不是简单优先文法。
\end{example}
